"""
解题思路：动态规划算法

    假设数组 nums 的值全都严格大于 00，那么一定有 dp[i] = dp[i - 1] + nums[i]。

    可是 dp[i - 1] 有可能是负数，于是分类讨论：
        如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；
        如果 dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]。

"""

#原始DP方程解法

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0 for x in range(len(nums))]

        dp[0] = nums[0]
        for i in range(1,len(nums)):
            if dp[i-1] > 0:
                dp[i] = dp[i-1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)


#优化空间版本

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = 0
        res = nums[0]
        for i in range(1,len(nums)):
            dp = max(dp+nums[i],nums[i])
            res = max(res,dp)
        return res